#include <unordered_map>

using namespace std;


// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


/**
 * @brief 给你一个链表的头节点 head ，判断链表中是否有环。
 */
class Solution {
public:
    // 141. 环形链表
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*, int> table;

        ListNode* curr = head;
        while (curr) {
            table[curr]++;
            if (table[curr] > 1) return true;
            curr = curr->next;
        }
        return false;
    }


    // 142. 环形链表 II
    ListNode* detectCycle(ListNode *head) {
        unordered_map<ListNode*, int> table;

        ListNode* curr = head;
        while (curr) {
            table[curr]++;
            if (table[curr] > 1) return curr;
            curr = curr->next;
        }

        return nullptr;
    }
};
